//#include<bits/stdc++.h>
//using namespace std;
//int a[5001][5001];
//long long f[5001];
//int main(){
//	int n,m;
//	cin>>n>>m;
//	int t1,t2;
//	for(int i = 0;i<m;i++){
//		cin>>t1>>t2;
//		a[t1][t2] = 1;
//	} 
//	f[n] = 1;
//	for(int i = n-1;i>0;i--){
//		for(int j = i+1;j<=n;j++){
//			if(a[i][j]==1)f[i]= (f[i]%80112002 + f[j]%80112002)%80112002;
//		}
//	}
//	cout<<f[1];
//	return 0;
//} 



#include<bits/stdc++.h>
using namespace std;
const int MAX = 5e3 +1;
int chu[MAX];
int ru[MAX];


int read(){
    int w = 0;
    char ch = 0;
    int x = 0;
    while(!isdigit(ch)){
        w |= ch == '-';
        ch = getchar();
    }
    while(isdigit(ch)){
        x = (x<<3) + (x<<1) + ch - 48;
        ch = getchar();
    }
    return w? -x : x;
}

char F[200];
void write(int x){
    if(x == 0){
    	putchar('0');
    	return;
	}
    int t = x;
    if(x<0){
        t = -x;
        putchar('-');
    }
    int cnt = 0;
    while(t>0){
        F[cnt++] = t%10 + 48;
        t /= 10;
    }
    while(cnt>0){
        putchar(F[--cnt]);

    }

}
int main(){
    int n,m;
    n = read();
    m = read();
    int t1,t2;
    int cur,next;
    vector<int> v[MAX];
    queue<int> q;
    vector<int> a(n+1);
    for(int i = 0;i<m;i++){
        t1 = read();
        t2 = read();
        ru[t2]++;
        chu[t1]++;
        v[t1].push_back(t2);
    }

    for(int i = 1;i<=n;i++){
        if(ru[i] == 0){
            q.push(i);
            a[i] = 1;
        }
    }
    while(!q.empty()){
        cur = q.front();
        q.pop();
        int len = v[cur].size();
        for(int i = 0;i<len;i++){
            next = v[cur][i];
            ru[next]--;
            a[next] = (a[cur] + a[next])%80112002;
            if(ru[next] == 0)q.push(next);
        }
    }
    int ans = 0;
    for(int i = 1;i<=n;i++){
        if(chu[i]==0){
            ans = (ans + a[i])%80112002;
        }
    }
    write(ans);
    return 0;
}
